import java.util.Arrays;
import java.util.List;

/*
要求：遍历数组，找到所有小于当前元素的左边元素个数，即右小数目
策略：归并排序，归并左右两个数组，取左边数组元素时右边已取元素个数为该元素当前有小数目
 */
public class GetRightLess {
}
class GetRightLessSolution {
    public List<Integer> countSmaller(int[] nums) {
        int n = nums.length;
        int[][] entrys = new int[n][3];
        for(int i=0;i<n;i++){
            entrys[i][0] = nums[i];
            entrys[i][1] = i;
        }
        mergeSort(entrys,0,n-1);
        Integer[] res = new Integer[n];
        for(int i=0;i<n;i++){
            res[entrys[i][1]] = entrys[i][2];
        }
        return Arrays.asList(res);
    }
    void mergeSort(int[][] entrys,int l,int r){
        if(l<r){
            int mid = (l+r)/2;
            mergeSort(entrys,l,mid);
            mergeSort(entrys,mid+1,r);
            merge(entrys,l,mid,r);
        }
    }
    void merge(int[][] entrys,int l,int m,int r){
        int[][] tmp = new int[r-l+1][3];
        int index = 0;
        int index1 = l;
        int index2 = m+1;
        while(index1<=m&&index2<=r){
            if(entrys[index1][0]<=entrys[index2][0]){//相等时，优先取左边，避免左边统计右小数目多计算
                entrys[index1][2] += index2-m-1;
                tmp[index++] = entrys[index1++];
            }
            else
                tmp[index++] = entrys[index2++];
        }
        while(index1<=m){
            entrys[index1][2] += index2-m-1;
            tmp[index++] = entrys[index1++];
        }
        while(index2<=r){
            tmp[index++] = entrys[index2++];
        }
        for(int i=l;i<=r;i++)
            entrys[i] = tmp[i-l];
    }
}